#include <iostream>
#include "singlelist.h"
#include "doublelist.h"
#include "singlelooplist.h"
#include "stack.h"
#include "queue.h"
#include "set.h"
#include "chainhash.h"
#include "openhash.h"
#include "binary_tree.h"
#include "binary_search_tree.h"

using namespace std;

void TestAlgoritbms();

void TestDataStruct();
void TestSingleList();
void TestDoubleList();
void TestSingleLoopList();
void TestStack();
void TestQueue();
void TestSet();
void TestChainHash();
void TestOpenHash();
void TestBinaryTree();
void TestBinarySearchTree();

int main()
{
    //TestAlgoritbms();
    TestDataStruct();

    return 0;
}

void TestAlgoritbms()
{

}

void TestDataStruct()
{
     //TestSingleList();

     //TestDoubleList();

     //TestSingleLoopList();

     //TestStack();

     //TestQueue();

     //TestSet();

     //TestChainHash();

     //TestOpenHash();

     //TestBinaryTree();

     TestBinarySearchTree();
}

void TestSingleList()
{
     singlelist::SingleList l;
     for (int i = 0; i < 6; ++i)
     {
         l.ListInsert(new singlelist::ListElmt(i));
     }
     singlelist::PrintSingleList(&l);

      cout << "after delete data...." << endl;
     singlelist::ListElmt* d = l.ListHead();
     d = d->GetNext()->GetNext()->GetNext();
     l.ListDelNext(d);
     singlelist::PrintSingleList(&l);
}

void TestDoubleList()
{
     doublelist::DoubleList l;
     for (int i = 0; i < 5; ++i)
     {
         l.ListInsert(new doublelist::ListElmt(i));
     }
     doublelist::PrintDoubleList(&l);

     cout << "after delete data...." << endl;
     doublelist::ListElmt* d = l.ListHead()->GetNext();
     l.ListDel(d);
     doublelist::PrintDoubleList(&l);
}

void TestSingleLoopList()
{
    singlelooplist::SingleLoopList l;
    singlelooplist::ListElmt* head = NULL;
    singlelooplist::ListElmt* d = NULL;
    for (int i = 0; i < 5; ++i)
    {
         d = new singlelooplist::ListElmt(i);
         l.ListInsert(head, d);
         head = d;
    }
    singlelooplist::PrintSingleLoopList(&l);

    head = l.ListHead();
    head = head->GetNext()->GetNext();
    cout << "after delete data...." << endl;
    l.ListDelNext(head);
    singlelooplist::PrintSingleLoopList(&l);
}

void TestStack()
{
    stackex::Stack s;
    for(int i = 0; i < 10; i++)
    {
        s.StackPush(i);
    }

    int data = -1;

    if (s.StackTop(data) == 0)
    {
        cout << "stack top: " << data << endl;
        cout << "stack size: " << s.StackSize() << endl;
    }


    s.StackPop(data);

    if (s.StackTop(data) == 0)
    {
        cout << "after pop data...." << endl;
        cout << "stack top: " << data << endl;
        cout << "stack size: " << s.StackSize() << endl;
    }
}

void TestQueue()
{
    queued::Queue q;
    for (int i = 0; i < 10; ++i)
    {
        q.QueueEnqueue(i);
    }

    int data = -1;
    if (q.QueueHead(data) == 0)
    {
        cout << "queue head: " << data << endl;
        cout << "queue size: " << q.QueueSize() << endl;
    }

    q.QueueDequeue(data);

    if (q.QueueHead(data) == 0)
    {
        cout << "after dequeue data...." << endl;
        cout << "queue head: " << data << endl;
        cout << "queue size: " << q.QueueSize() << endl;
    }

}

void TestSet()
{
    setex::Set s;
    for (int i = 0; i < 5; ++i)
    {
        s.SetInsert(i);
    }
    setex::PrintSet(&s);

    setex::Set sub;
    for (int i = 0; i < 3; ++i)
    {
        sub.SetInsert(i);
    }

    if (s.IsSetSubset(&sub))
    {
        cout << "subset!" << endl;
    }

    sub.SetInsert(3);
    sub.SetInsert(4);
    if (s.IsSetEqual(&sub))
    {
        cout << "set equal!" <<endl;
    }

    setex::Set se;
    for (int i = 3; i < 10; ++i)
    {
        se.SetInsert(i);
    }

    cout << "difference set:" << endl;
    setex::Set* ret = s.SetDifference(&se);
    if  (ret)
    {
        setex::PrintSet(ret);
    }

    cout << "intersection set:" << endl;
    ret = s.SetIntersection(&se);
    if (ret)
    {
        setex::PrintSet(ret);
    }

    cout << "union set:" << endl;
    ret = s.SetUnion(&se);
    if (ret)
    {
        setex::PrintSet(ret);
    }

    cout << "after delete...." << endl;
    s.SetRemove(2);
    setex::PrintSet(&s);

    cout << "after insert...." << endl;
    s.SetInsert(7);
    setex::PrintSet(&s);
}

void TestChainHash()
{
    hashtable::ChainHashTable h(1699);
    for (int i = 0; i < 100; ++i)
    {
        h.ChtblInsert(i, i);
    }

    cout << "hash table size: " << h.GetHashSize() << endl;

    int k = 10;
    int d = 0;
    if (h.ChtblLookup(k,d))
    {
        cout << "key: " << k << " value: " << d << endl;
    }

    h.ChtblDel(k);
    cout << "after delete one key...." << endl;
    cout << "hash table size: " << h.GetHashSize() << endl;
}

void TestOpenHash()
{
    hashtable::OpenHashTable h(1699);
    for (int i = 0; i < 100; ++i)
    {
        h.OhtblInsert(i, i);
    }

    cout << "hash table size: " << h.GetHashSize() << endl;

    int k = 10;
    int d = 0;
    if (h.OhtblLookup(k, d))
    {
        cout << "key: " << k << " value: " << d << endl;
    }

    h.OhtblDel(k);
    cout << "after delete one key...." << endl;
    cout << "hash table size: " << h.GetHashSize() << endl;
}

void TestBinaryTree()
{
    binarytree::BinaryTree tree(20);
    for (int i = 0; i < 20; ++i)
    {
        tree.TreeInsert(i);
    }

    cout << "pre order: ";
    tree.Preorder();
    cout << "in order: ";
    tree.Inorder();
    cout << "post order: ";
    tree.Postorder();
    cout << "level order: ";
    tree.Levelorder();
}

void TestBinarySearchTree()
{
    binarysearchtree::BinarySearchTree tree(20);
    int data[11] = {15,6,18,3,7,17,20,2,4,13,9};
    for (int i = 0; i < 11; ++i)
    {
        tree.InsertData(data[i]);
    }

    cout << "in order: ";
    tree.Inorder();
    cout << "min value: " << tree.MinValue() << endl;
    cout << "max value: " << tree.MaxValue() << endl;

    tree.DelData(13);
    cout << "after delete, in order:";
    tree.Inorder();
}
